package subject1.designQuestion;

import java.util.Iterator;
import java.util.PriorityQueue;

class ExamRoom {
    class LeftRightInterval {
        int left;
        int right;
        int interval;

        public LeftRightInterval(int left, int right, int interval) {
            this.left = left;
            this.right = right;
            this.interval = interval;
        }

        int getMiddle() {
            return (left + right) >> 1;
        }
    }

    private PriorityQueue<LeftRightInterval> queue = new PriorityQueue<>((o1, o2) -> o1.interval / 2 == o2.interval / 2 ? o1.left - o2.left : o2.interval - o1.interval);
    private int n;
    private int cnt;
    public ExamRoom(int n) {
        this.n = n;
    }
    
    public int seat() {
        cnt++;
        if (cnt == 1) {
            return 0;
        } else if (cnt == 2) {
            queue.add(new LeftRightInterval(0, n - 1, n));
            return n - 1;
        }

        // 获取间隔最大的相邻学生的座位号
        LeftRightInterval leftRightInterval = queue.poll();
        int middle = leftRightInterval.getMiddle();
        LeftRightInterval newLeftRightInterval = new LeftRightInterval(middle, leftRightInterval.right, leftRightInterval.right - middle);
        queue.add(newLeftRightInterval);
        leftRightInterval.right = middle;
        leftRightInterval.interval = leftRightInterval.right - leftRightInterval.left;
        queue.add(leftRightInterval);

        return middle;
    }

    public void leave(int p) {
        if (cnt == 2 && queue.size() == 1) {
            queue.poll();
        } else if (cnt > 2) {
            LeftRightInterval obj1 = null;
            LeftRightInterval obj2 = null;
            Iterator<LeftRightInterval> iterator = queue.iterator();
            while (iterator.hasNext()) {
                LeftRightInterval leftRightInterval = iterator.next();
                if (leftRightInterval.right == p) {
                    obj1 = leftRightInterval;
                } else if (leftRightInterval.left == p) {
                    obj2 = leftRightInterval;
                }
            }
            if (obj1 == null) {
                queue.remove(obj2);
            } else if (obj2 == null) {
                queue.remove(obj1);
            } else {
                queue.remove(obj1);
                obj1.right = obj2.right;
                obj1.interval = obj1.right - obj1.left;
                queue.add(obj1);
                queue.remove(obj2);
            }
        }
        cnt--;
    }

    public static void main(String[] args) {
        /*ExamRoom examRoom = new ExamRoom(10);
        System.out.println(examRoom.seat());
        System.out.println(examRoom.seat());
        System.out.println(examRoom.seat());
        System.out.println(examRoom.seat());
        examRoom.leave(4);
        System.out.println(examRoom.seat());*/
        ExamRoom examRoom = new ExamRoom(10);
        System.out.println(examRoom.seat());
        System.out.println(examRoom.seat());
        System.out.println(examRoom.seat());
        examRoom.leave(0);
        examRoom.leave(4);
    }
}
